package com.hdu.other.dp.maxIncLen;

import java.util.Arrays;

public class lc354 {
    class Solution {
        public int maxEnvelopes(int[][] envelopes) {
            Arrays.sort(
                    envelopes,
                    (a, b) -> {
                        if (a[0] == b[0]) {
                            return b[1] - a[1];
                        } else {
                            return a[0] - b[0];
                        }
                    }
            );
            int[] ends = new int[envelopes.length];
            int len = 0;
            for (int[] envelope : envelopes) {
                int index = bs(ends, len, envelope[1]);
                if (index == -1) {
                    ends[len++] = envelope[1];
                } else {
                    ends[index] = envelope[1];
                }
            }
            return len;
        }

        int bs(int[] ends, int len, int target) {
            int l = 0, r = len - 1, ans = -1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (ends[mid] >= target) {
                    ans = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            return ans;
        }
    }
}
